package com.lw.leetcode.bingChaJi.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * b
 * bingchaji
 * 2492. 两个城市间路径的最小分数
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/4 12:32
 */
public class MinScore {

    public int minScore(int n, int[][] roads) {
        int[] arr1 = new int[n + 1];
        int[] arr2 = new int[n + 1];
        Arrays.fill(arr2, Integer.MAX_VALUE);
        for (int i = 1; i <= n; i++) {
            arr1[i] = i;
        }
        for (int[] road : roads) {
            int a = road[0];
            int b = road[1];
            int c = road[2];
            arr2[a] = Math.min(arr2[a], c);
            arr2[b] = Math.min(arr2[b], c);
            int a1 = find(arr1, a);
            int b1 = find(arr1, b);
            if (a1 != b1) {
                arr1[Math.max(a1, b1)] = Math.min(a1, b1);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int a = find(arr1, i);
            if (a == 1) {
                min = Math.min(min, arr2[i]);
            }
        }
        return min;
    }

    private int find(int[] arr, int a) {
        if (arr[a] == a) {
            return a;
        }
        int t = find(arr, arr[a]);
        arr[a] = t;
        return t;
    }

}
